Large closed loop control systems have many components that run as tasks in groups in a cyclic manner. An example of such a system is an automated Computer Aided Dispatcher for Railway Networks. Such control systems manage environments often with hundreds of components in several groups and where the tasks for these components arrive concurrently. Tasks in a group are independent. These complete their computation and release the resources held, if any, before the tasks in the next group run.
As tasks in such closed loop control systems run again and again in a cyclic manner, the control systems can easily collect and maintain a history of run-times of the tasks (average processing time μ and standard deviation σ) with very little overheads. However, Operating System (OS) does not use such a history of run-times for the purpose of scheduling tasks. OS scheduler typically, for example the LINUX Completely Fair Scheduler, uses priority of tasks and tries to be fair to them by allowing them to run for small intervals of time (time-slice) at a time and modifying subsequent time-slices for each task depending on the CPU-time consumed by a task and its priority.
Several attempts/researches have been made to schedule and run tasks using heuristics in an efficient manner. Research paper authored by J. N. D. GUPTA and A. J. RUIZ-TORRES, published in 2001 (hereinafter referred as Gupta et. al.), describes three known bin-packing based heuristics and a new heuristic in A LISTFIT heuristic for minimizing make span on identical parallel machines, Production Planning & Control: The Management of Operations. Another research paper authored by Laha and Behera (hereinafter referred as Laha et. al.) in 2015 provides a comprehensive review of the heuristics described in the paper authored by Gupta et. al. and presents an experimental framework to investigate performance of these heuristics. Another research paper authored by Lee et. al. in 2005 proposed using LPT heuristic, generation of a schedule and then using simulated annealing to improve on it in-order to generate a near-optimal solution. Cossari et. al. published in 2011 describes an algorithm for multiprocessor scheduling problem with the objective of minimizing the normalized sum of square for workload deviations (NSSWD). Gregg et. al. published in 2011 presents a method for dynamically scheduling applications running on heterogeneous platforms (multi-core CPU and many-core GPU) in order to maximize overall throughput. Their method estimates when an application would finish execution on a given resource based on historical run-time information. All the above methods make use of the expected processing time (μ) of the tasks to create a predictive un-ordered list. However, in reality, there would be differences between the actual run-times and expected processing time (μ). When the deviations are large, the actual make-spans generated by these heuristics can be significantly larger than expectations due to possible imbalances over the parallel machines.